This invention relates to arbitrating requests by devices in a computer system for a shared resource and more particularly to an arbiter that grant bus requests using an arbitration scheme that maximizes bus utilization through transaction prediction.
Arbiters are used in computer systems to control access to a common bus used by multiple devices. Arbiters insure that only a single device uses the bus at one time, and that all requesting devices are fairly allocated use of the bus. Arbiters use various arbitration schemes to grant access to each requesting device based on an algorithm that attempts to insure fair access to the shared bus. Various common algorithms exist such as round-robin, rotating priority, weighted priority, and history-based arbitration. Arbiters based on these algorithms are typically limited to observing a request per device and generating a grant per device, with the possible inclusion of a minimum number of bus control signals to synchronize the arbitration according to the bus protocol. Specifically, these arbiters are limited in scope to allowing each device ‘access’ to a bus, without taking into account the transactions generated by the devices once they are granted access. While this limitation allows the arbiter itself to be relatively simple compared to the operation of the associated bus, it deprives the arbiter of state information that would be useful in further determining if a device should be granted. More specifically, it prevents the arbiter from predicting the type of bus transaction a requestor will issue once granted the bus. Without this state information, granted devices can issue transactions that will predictably not result in the transfer of data, resulting in degraded bus bandwidth and increased latency for all devices sharing the bus. Predicting the type of bus transaction a requestor will issue if granted the bus allows the arbiter to prioritize the requesters in a manner that maximizes bus utilization.